package com.lds.offer.demo;

import com.lds.offer.entity.BinaryTreeNode;
import com.lds.offer.entity.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @description: Offer 34. 二叉树中和为某一值的路径
 * @author: lds
 * @create: 2022-10-09 14:35
 **/
public class Offer_34_二叉树中和为某一值的路径 {

    //https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

    /**
     * 要求找出根节点到叶节点和等于target的路径
     * 树状图先序遍历为：根左右
     * 我们按照先序遍历一步一步向下遍历树
     * 定义一个list用于存放路径，定义一个result集合用于存放和等于target的路径
     * 我们先使用一个list用来存储遍历到的节点路径，同时target减去当前节点的值
     * 直到当前节点没有叶节点（即没有左右节点）并且target=0（即和相加等于target）时，该list存放的节点路径即为相加和为target的路径
     * 我们将这个list加入result结果集中
     * 如果当前节点遍历完成后target！=0时，我们将改节点从list中移除（这一步相当于将节点回到父节点位置，继续向下遍历其他节点）
     */


    public static LinkedList<Integer> path = new LinkedList<>();
    public static LinkedList<List<Integer>> result = new LinkedList<>();

    public static void main(String[] args) {
        BinaryTreeNode init = BinaryTreeNode.init();
        print(init,66);
        System.out.println(result);
    }

    public static void print(BinaryTreeNode node,int target) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        target -= node.val;
        if (target == 0 && node.left == null && node.right == null) {
            result.add(new LinkedList<>(path));
        }
        print(node.left,target);
        print(node.right,target);
        path.removeLast();
    }

}
